/*
 * @Author: kaikaima
 * @Date: 2020-11-22 21:45:57
 * @LastEditTime: 2020-12-25 04:59:10
 * @LastEditors: Please set LastEditors
 * @Description: try to add annotations
 * @FilePath: /undefined/home/messi/Data_Structure_and_Algorithm_GIT/Tree/BST.h
 */
#ifndef __hhxxttxs_BST__
#define __hhxxttxs_BST__

#include <iostream>

#define BLACK true
#define RED false

template <class T>
class BinaryTree
{
protected:
    class Node
    {
    public:
	T data;
	Node* lc;
	Node* rc;
	Node* parent;
    bool color;
    Node() {lc=rc=parent=NULL; color=BLACK;};
	Node(T _data);
    };
    Node* root;    
    Node* nil;
    /**
     * @description: I hope that the parent of root is NULL while leaf note is nil. 
     * @param {*}
     * @return {*}
     */
    void release(Node* _x);
    Node* successor(Node* _x) const;
    Node* predecessor(Node* _x) const;
    Node* min(Node* _x) const;
    Node* max(Node* _x) const;
    Node* tree_search(T _data) const;
    void inorder_walk(Node* _x) const;
    void change(Node* _u, Node* _v);
    int DEL(Node* _x);
    Node* data_insert(T _data);
public:
    BinaryTree() {nil=new Node; nil->color=BLACK; nil->parent=NULL; root=nil;};
    BinaryTree(T _data);
    ~BinaryTree();
    void insert(T _data);
    bool Search(T _data) const;
    T get_min() const;
    T get_max() const;
    void inorder_walk() const;
    void del_data(T _data);
};

template <class T>
BinaryTree<T>::Node::Node(T _data)
{
    data = _data;
    parent = lc = rc = NULL;
    color = BLACK;
};

template <class T>
void BinaryTree<T>::release(Node* _x)
{
    if (_x != nil)
    {
	release(_x->lc);
	release(_x->rc);
	delete _x;
    }	
};

/**
 * @description: 
 * @param {*} a note _x
 * @return {*} the min note whose data is bigger than _x's. 
 */
template <class T>
typename BinaryTree<T>::Node* BinaryTree<T>::successor(BinaryTree<T>::Node* _x) const
{
    Node* x = _x;
    if (x->rc != nil)
	return min(x->rc);
    Node* y = x->parent;
    while (y != NULL && x == y->rc)
    {
	x = y;
	y = y->parent;
    }
    return y;
};

/**
 * @description: 
 * @param {*} a note _x
 * @return {*} the max note whose data is smaller than _x's. 
 */
template <class T>
typename BinaryTree<T>::Node* BinaryTree<T>::predecessor(Node* _x) const
{
    Node* x = _x;
    if (x->lc != nil)
	return max(x->lc);
    Node* y = x->parent;
    while (y != NULL && x == y->lc)
    {
	x = y;
	y = y->parent;
    }
    return y;
};

template <class T>
typename BinaryTree<T>::Node* BinaryTree<T>::min(Node* _x) const
{
    while (_x->lc != nil)
	_x = _x->lc;
    return _x;
};

template <class T>
typename BinaryTree<T>::Node* BinaryTree<T>::max(Node* _x) const
{
    while (_x->rc != nil)
	_x = _x->rc;
    return _x;
};

template <class T>
typename BinaryTree<T>::Node* BinaryTree<T>::tree_search(T _data) const
{
    Node* p = root;
    while (p != nil && p != NULL){
    if(p->data < _data)
    p = p->rc;
    else if(p->data > _data)
    p = p->lc;
    else
    break;}
    if(p==nil)
    return NULL;
    return p;
};

template <class T>
void BinaryTree<T>::inorder_walk(Node* _x) const
{
    if (_x != nil)
    {
	inorder_walk(_x->lc);
	std::cout << _x->data << "\t";
	inorder_walk(_x->rc);
    }
};

/**
 * @description: the node _u will not be deleted for follow-up actions
 * @param {*} two nodes _u _v
 * @return {*} change _u to _v
 */
template <class T>
void BinaryTree<T>::change(Node* _u, Node* _v)
{
    if(_u != NULL && _u != nil)
    /**
     * @description: a new node may be NULL
     * @param {*}
     * @return {*}
     */
    {
        if(_u->parent == NULL)
        root=_v;
        else if(_u==_u->parent->lc)
        _u->parent->lc=_v;
        else
        _u->parent->rc=_v;
        if(_v!=nil)
        _v->parent=_u->parent;
    }   
};

/**
 * @description: if _x has two kids, find the min of _x's rightchild, change it to _x and delete _x. 
 *               It is equal to the following. 
 * @param {*}
 * @return {*}
 */
template <class T>
int BinaryTree<T>::DEL(Node* _x)
{
    if(_x==NULL || _x==nil)
    return 0;
    if(_x->rc==nil){
        change(_x,_x->lc);
        delete _x;
    }
    else if(_x->lc==nil){
        change(_x,_x->rc);
        delete _x;
    }
    else{
    Node* p = min(_x->rc);
    change(p,p->rc);
    _x->data=p->data;
    delete p;
    }
    return 0;
};

/**
 * @description: 
 * @param {*} a data
 * @return {*} address of the new node
 */
template <class T>
typename BinaryTree<T>::Node* BinaryTree<T>::data_insert(T _data)
{
    Node* y = NULL;
    Node* x = root;
    Node* p = new Node(_data);
    p->lc = p->rc = nil;
    while (x != nil){
	y = x;
	if (p->data < x->data)
	x = x->lc;
	else
	x = x->rc;
    }
    p->parent = y;
    if (y == NULL)
	root = p;
    else{
    p->color=RED;
    if (p->data < y->data)
	y->lc = p;
    else
	y->rc = p;
    }
    return p;
};

/*
 *                     江城子 . 分割符
 *           ————上面是private，下面是public
 * 
 *               十年生死两茫茫，写程序，到天亮。
 *                    千行代码，Bug何处藏。
 *               纵使码完又怎样，朝令改，夕断肠。
 * 
 *               老师每周新作业，天天改，日日忙。
 *                    相顾无言，惟有泪千行。
 *               每晚灯火阑珊处，夜难寐，加班狂。
 * 
 */


template <class T>
BinaryTree<T>::BinaryTree(T _data)
{
    nil=new Node;
    nil->color=BLACK;
    Node* p = new Node(_data);
    p->lc=p->rc=nil;
    root=p;
};

template <class T>
BinaryTree<T>::~BinaryTree()
{
    release(root);
    delete nil;
};

template <class T>
void BinaryTree<T>::insert(T _data)
{
    data_insert(_data);
};

template <class T>
bool BinaryTree<T>::Search(T _data) const
{
    if(tree_search(_data) != NULL)
    return true;
    else
    return false;
};

template <class T>
T BinaryTree<T>::get_min() const
{
    return min(root)->data;
};

template <class T>
T BinaryTree<T>::get_max() const
{
    return max(root)->data;
};

template <class T>
void BinaryTree<T>::inorder_walk() const
{
    if (root != nil)
	inorder_walk(root);
    else
    std::cout<<"It's an empty tree. ";
    std::cout<<std::endl;
};

template <class T>
void BinaryTree<T>::del_data(T _data)
{
    DEL(tree_search(_data));
};

#else
//do nothing
#endif
